import com.kiwi.nixu.common.LNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

/**
 * @Author: zqb
 * @Description: //TODO
 * @Date: Created in 18:00 2020/12/6
 * @Create By:
 * <p>
 * 给定一个带头结点的单链表，请将其逆序。
 * 即如果单链表原来为head→1→2→3→4→5→6→7，则逆序后变为head→7→6→5→4→3→2→1
 */
public class A如何实现链表的逆序 {

    /**
     * 分析与解答：由于单链表与数组不同，单链表中每个结点的地址都存储在其前驱结点的指针域中，
     * 因此，对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。
     * 在对链表的操作过程中，需要特别注意在修改结点指针域的时候，记录下后继结点的地址，
     * 否则会丢失后继结点
     */


    /**
     * 时间复杂度O(N)
     * 空间复杂度O(1)
     */
    private class AA就地逆序 {

    }


    /**
     * 时间复杂度O(N)
     * 空间复杂度O(1)
     */
    private class AB递归法 {

    }

    /**
     * 以上这种方法也只需要对单链表进行一次遍历，
     * 因此，时间复杂度为O（N）。其中，N为链表的长度。
     * 与方法一相比，这种方法不需要保存前驱结点的地址，
     * 与方法二相比，这种方法不需要递归地调用，效率更高
     */
    private static class AC插入法 {

        /**
         * 插入法的主要思路：
         * 从链表的第二个结点开始，把遍历到的结点插入到头结点的后面，
         * 直到遍历结束。假定原链表为head→1→2→3→4→5→6→7，在遍历到2时，
         * 将其插入到头结点后，链表变为head→2→1→3→4→5→6→7，
         * 同理将后序遍历到的所有结点都插入到头结点head后，
         * 就可以实现链表的逆序
         * <p>
         * 有头结点
         */
        public static void reverseWithHead(LNode head) {
            if (head == null || head.next == null) {
                return;
            }
            LNode cur = null;
            LNode next = null;
            cur = head.next.next;
            //设置链表第一个节点为尾节点
            head.next.next = null;
            //把遍历到节点插入到头结点的后面
            while (cur != null) {
                next = cur.next;
                cur.next = head.next;
                head.next = cur;
                cur = next;
            }
        }

        /**
         * 没有头结点
         *
         * @param head
         */
        public static LNode reverseNoWithHead(LNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            //前驱节点
            LNode pre = head;
            LNode cur = head.next;
            LNode next;
            pre.next = null;

            //使当前遍历到的节点cur指向其前驱节点
            while (cur != null) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }

        public static void main(String[] args) {
            //LNode head = new LNode();
            //head.next = null;
            //head.data = 1;
            //LNode tmp = null;
            //LNode cur = head;
            //for (int i = 1; i < 2; i++) {
            //    tmp = new LNode();
            //    tmp.data = i%2;
            //    tmp.next = null;
            //    cur.next = tmp;
            //    cur = tmp;
            //}
            //LNode lNode =new LNode(1);
            //LNode lNode2 =new LNode(2);
            //LNode lNode3 =new LNode(3);
            //LNode lNode4 =new LNode(4);
            //LNode lNode5 =new LNode(5);
            //LNode lNode6 =new LNode(6);
            //lNode.next=lNode2;
            //lNode2.next=lNode3;
            //lNode3.next=lNode4;
            //lNode4.next=lNode5;
            //lNode5.next=lNode6;
            //System.out.println("逆序前");
            //for (cur = head; cur != null; cur = cur.next) {
            //    System.out.print(cur.data + " ");
            //}
            //System.out.println("\n逆序后：");
            ////reverseWithHead(head);
            //head = reverseNoWithHead(head);
            //for (cur = head; cur != null; cur = cur.next) {
            //    System.out.print(cur.data + " ");
            //}
            //LNode lNode =new LNode(1);
            //LNode lNode2 =new LNode(2);
            //LNode lNode3 =new LNode(4);
            //lNode.next=lNode2;
            //lNode2.next=lNode3;
            //
            //LNode lNode11 =new LNode(1);
            //LNode lNode12 =new LNode(3);
            //LNode lNode12 =new LNode(3);
            //LNode lNode12 =new LNode(3);
            //LNode lNode13 =new LNode(4);
            //lNode11.next=lNode12;
            //lNode12.next=lNode13;
            //LNode lNode1 = mergeTwoLists(lNode, lNode11);
            LNode lNode0 =new LNode(1);
            LNode lNode1 =new LNode(1);
            LNode lNode2 =new LNode(1);
            LNode lNode3 =new LNode(2);
            LNode lNode4 =new LNode(2);
            LNode lNode5 =new LNode(2);
            LNode lNode6 =new LNode(2);
            LNode lNode7 =new LNode(3);
            LNode lNode8 =new LNode(4);
            LNode lNode9 =new LNode(4);
            LNode lNode10 =new LNode(5);
            lNode0.next=lNode1;
            lNode1.next=lNode2;
            lNode2.next=lNode3;
            lNode3.next=lNode4;
            lNode4.next=lNode5;
            lNode5.next=lNode6;
            lNode6.next=lNode7;
            lNode7.next=lNode8;
            lNode8.next=lNode9;
            lNode9.next=lNode10;

            LNode lNode = deleteDuplicates1(lNode0);
            System.out.println(lNode.data);
        }

        public boolean hasCycle(LNode head) {
            LNode first;
            LNode second;
            for(first=head,second =head.next;;first=first.next,second=second.next){
                if(first==second){
                    return true;
                }
            }
        }

        public static LNode deleteDuplicates1(LNode head) {
            if (head == null || head.next == null) {
                return head;
            }

            head.next = deleteDuplicates1(head.next);

            return head.data == head.next.data ? head.next : head;
        }


        public static LNode deleteDuplicates(LNode head) {
            LNode firstNode=head;
            while (head!=null){
                head.next=digui(head);
                head=head.next;
            }
            return firstNode;
        }
        public static LNode digui(LNode head){
            if(head.next==null){
                return null;
            }else{
                if(head.data.equals(head.next.data)){
                    return digui(head.next);
                }else{
                    return head.next;
                }
            }
        }

        public static LNode mergeTwoLists(LNode l1, LNode l2) {
            //构建一个新的链表
            LNode newListNode=new LNode(-1);

            while(l1!=null && l2!=null){
                if(l1.data <l2.data){
                    newListNode.next=l1;
                    l1=l1.next;
                }else{
                    newListNode.next=l2;
                    l2=l2.next;
                }
                newListNode.next.next=null;
            }
            HashSet set = new HashSet<>();
            Iterator iterator = set.iterator();
            while (iterator.hasNext()){
                iterator.next();
            }

                newListNode.next=(l1!=null?l1:l2);
            return newListNode.next;
        }

        public static LNode middleNode(LNode head) {
            int oneStep=1;
            while(head!=null){
                int doubleStep=oneStep;
                LNode tmp=head.next;
                System.out.println("遍历当前节点的数据为:"+head.data);
                while(doubleStep>0){
                    if( tmp!=null){
                        System.out.print(tmp.data +" ");
                        tmp=tmp.next;
                        doubleStep--;
                    }else{
                        if(doubleStep%2==1){
                            return head;
                        }else{
                            return head.next;
                        }
                    }
                }
                head=head.next;
                oneStep++;
            }
            return null;
        }

        public static int getDecimalValue(LNode head) {
            int c=0;
            while(head!=null){
                if(head.data==1 ){
                    if(c==0){
                        c=1;
                    }else{
                        c<<=1;
                        c|=1;
                    }
                }else{
                    if(c!=0){
                        c<<=1;
                    }
                }
                head=head.next;
            }
            return c;
        }

    }


    /**
     * 对不带头结点的单链表进行逆序
     */
    private class AD对不带头结点的单链表进行逆序 {

    }

    /**
     * 对不带头结点的单链表进行逆序
     */
    private class AE从尾到头输出链表 {


    }
}
